package Hot_100;

import java.util.*;

/*
* 17.   电话号码的字母组合
        给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
        给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
* */

public class T17_letterCombinations {

    public List<String> letterCombinations_1(String digits) {
        ArrayList<String> ans = new ArrayList<>();  //结果集
        HashMap<Character, String> numberTable = new HashMap<Character, String>(){{ //数字映射表
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        if (digits.length() == 0) {
            return ans;
        }
        DFS(digits, numberTable, 0, new StringBuffer(), ans);
        return ans;
    }



    /***
     *
     * @param digits 提供的数字串
     * @param numberTable  数字映射表
     * @param index 数字串的指针
     * @param res   一个结果
     * @param ans   结果集
     */
    public void DFS(String digits, HashMap<Character, String> numberTable, int index,StringBuffer res,ArrayList<String> ans) {
        if (index == digits.length() ) { //递归出口
            ans.add(res.toString());
            return;
        }

        char ch = digits.charAt(index);
        String str = numberTable.get(ch);
        for (int i = 0; i < str.length(); i++) {
            res.append(str.charAt(i));
            DFS(digits, numberTable, index + 1, res, ans); //下一层
            res.deleteCharAt(index);    //回溯
        }
    }


//    ---------------------------------------------------------------------------------------
    public List<String> letterCombinations_2(String digits) {
        ArrayList<String> ans = new ArrayList<>();  //结果集
        HashMap<Character, String> numberTable = new HashMap<Character, String>(){{ //数字映射表
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        if (digits.length() == 0) {
            return ans;
        }

        BFS(digits, numberTable, ans);
        return ans;
    }

    public void BFS(String digits, HashMap<Character, String> numberTable,ArrayList<String> ans) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node( "", 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.index == digits.length()) { //到达终点,找到一种解法
                ans.add(node.value);
            }else{
                char num = digits.charAt(node.index);
                String str = numberTable.get(num);
//                String str = numberTable.get(node.num);
                for (int i = 0; i < str.length(); i++) {
                    queue.offer(new Node(node.value+str.charAt(i), node.index + 1));
                }
            }
        }
    }
}


class Node{
//    char num;       //记录数字串中对应的数
    String value;   //拼凑的字符串
    int index;      //记录数字串的下一个索引

    public Node(String value, int index) {
        this.value = value;
        this.index = index;
    }
}